/*
给定一个二叉搜索树和一个目标结果，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。

案例 1:

输入: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 9

输出: True
 

案例 2:

输入: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 28

输出: False

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum-iv-input-is-a-bst
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    bool DEBUG=true;
    unordered_set<int> uoset;
public:
    bool findTarget(TreeNode* root, int k) {
        inorder(root);
        unordered_set<int>::iterator it;
        unordered_set<int>::iterator tmp;
        for(it=uoset.begin();it!=uoset.end();it++){
            if(DEBUG){
                cout<<*it<<endl;
            }
            tmp=uoset.find(k-(*it));
            if(tmp!=uoset.end()&&tmp!=it){
                return true;
            }
        }
        return false;
    }

    void inorder(TreeNode* root){
        if(root!=NULL){
            inorder(root->left);
            uoset.insert(root->val);
            if(DEBUG){
                cout<<"hash_set insert:"<<root->val<<endl;
            }
            inorder(root->right);
        }
    }
};